#include<bits/stdc++.h>
using namespace std;

struct Stack{
    int num[200010];
    int siz = 0;
    int top = -1;

    void Push(int x){
        top++;
        num[top] = x;
        siz++;
    }
    void Pop(){
        num[top--] = 0;
        siz--;
    }
    int Size(){
        return siz;
    }
    int Top(){
        return num[top];
    }
};
Stack st;
vector<int> res; // 存储当前已出栈的序列
int n, ans = 0; // ans:合法序列个数

void dfs(int now){ // now表示下一个要入栈的数字
    if(res.size() == n){ // 已形成完整的出栈序列
        for(int i = 0; i < n; ++i){
            cout << res[i] << " \n"[i == n-1];
        }
        ans++;
        return;
    }
    if(st.Size()){ // 出栈
        int pre = st.Top(); // 保留栈顶元素用于回溯
        res.push_back(pre);
        st.Pop();
        dfs(now);
        st.Push(pre);
        res.pop_back();
    }
    if(now <= n){ // 入栈
        st.Push(now);
        dfs(now+1);
        st.Pop();
    }
}
int main(){
    cin >> n;
    dfs(1);
    cout << ans << '\n';
    return 0;
}